home *** CD-ROM | disk | FTP | other *** search
/ Dr. Windows 3 / dr win3.zip / dr win3 / NEW_TECH / AWKSRC.ZIP / ARRAY.C < prev    next >
C/C++ Source or Header  |  1992-11-02  |  7KB  |  281 lines
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* 
  6.  * Copyright (C) 1986, 1988, 1989, 1991, 1992 the Free Software Foundation, Inc.
  7.  * 
  8.  * This file is part of GAWK, the GNU implementation of the
  9.  * AWK Progamming Language.
  10.  * 
  11.  * GAWK is free software; you can redistribute it and/or modify
  12.  * it under the terms of the GNU General Public License as published by
  13.  * the Free Software Foundation; either version 2 of the License, or
  14.  * (at your option) any later version.
  15.  * 
  16.  * GAWK is distributed in the hope that it will be useful,
  17.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19.  * GNU General Public License for more details.
  20.  * 
  21.  * You should have received a copy of the GNU General Public License
  22.  * along with GAWK; see the file COPYING.  If not, write to
  23.  * the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  24.  */
  25.  
  26. #include "awk.h"
  27.  
  28. static NODE *assoc_find P((NODE *symbol, NODE *subs, int hash1));
  29.  
  30. NODE *
  31. concat_exp(tree)
  32. register NODE *tree;
  33. {
  34.     register NODE *r;
  35.     char *str;
  36.     char *s;
  37.     unsigned len;
  38.     int offset;
  39.     int subseplen;
  40.     char *subsep;
  41.  
  42.     if (tree->type != Node_expression_list)
  43.         return force_string(tree_eval(tree));
  44.     r = force_string(tree_eval(tree->lnode));
  45.     if (tree->rnode == NULL)
  46.         return r;
  47.     subseplen = SUBSEP_node->lnode->stlen;
  48.     subsep = SUBSEP_node->lnode->stptr;
  49.     len = r->stlen + subseplen + 2;
  50.     emalloc(str, char *, len, "concat_exp");
  51.     memcpy(str, r->stptr, r->stlen+1);
  52.     s = str + r->stlen;
  53.     free_temp(r);
  54.     tree = tree->rnode;
  55.     while (tree) {
  56.         if (subseplen == 1)
  57.             *s++ = *subsep;
  58.         else {
  59.             memcpy(s, subsep, subseplen+1);
  60.             s += subseplen;
  61.         }
  62.         r = force_string(tree_eval(tree->lnode));
  63.         len += r->stlen + subseplen;
  64.         offset = s - str;
  65.         erealloc(str, char *, len, "concat_exp");
  66.         s = str + offset;
  67.         memcpy(s, r->stptr, r->stlen+1);
  68.         s += r->stlen;
  69.         free_temp(r);
  70.         tree = tree->rnode;
  71.     }
  72.     r = make_str_node(str, s - str, ALREADY_MALLOCED);
  73.     r->flags |= TEMP;
  74.     return r;
  75. }
  76.  
  77. /* Flush all the values in symbol[] before doing a split() */
  78. void
  79. assoc_clear(symbol)
  80. NODE *symbol;
  81. {
  82.     int i;
  83.     NODE *bucket, *next;
  84.  
  85.     if (symbol->var_array == 0)
  86.         return;
  87.     for (i = 0; i < HASHSIZE; i++) {
  88.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  89.             next = bucket->ahnext;
  90.             unref(bucket->ahname);
  91.             unref(bucket->ahvalue);
  92.             freenode(bucket);
  93.         }
  94.         symbol->var_array[i] = 0;
  95.     }
  96. }
  97.  
  98. /*
  99.  * calculate the hash function of the string in subs
  100.  */
  101. unsigned int
  102. hash(s, len)
  103. register char *s;
  104. register int len;
  105. {
  106.     register unsigned long h = 0, g;
  107.  
  108.     while (len--) {
  109.         h = (h << 4) + *s++;
  110.         g = (h & 0xf0000000);
  111.         if (g) {
  112.             h = h ^ (g >> 24);
  113.             h = h ^ g;
  114.         }
  115.     }
  116.     if (h < HASHSIZE)
  117.         return h;
  118.     else
  119.         return h%HASHSIZE;
  120. }
  121.  
  122. /*
  123.  * locate symbol[subs]
  124.  */
  125. static NODE *                /* NULL if not found */
  126. assoc_find(symbol, subs, hash1)
  127. NODE *symbol;
  128. register NODE *subs;
  129. int hash1;
  130. {
  131.     register NODE *bucket, *prev = 0;
  132.  
  133.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  134.         if (cmp_nodes(bucket->ahname, subs) == 0) {
  135.             if (prev) {    /* move found to front of chain */
  136.                 prev->ahnext = bucket->ahnext;
  137.                 bucket->ahnext = symbol->var_array[hash1];
  138.                 symbol->var_array[hash1] = bucket;
  139.             }
  140.             return bucket;
  141.         } else
  142.             prev = bucket;    /* save previous list entry */
  143.     }
  144.     return NULL;
  145. }
  146.  
  147. /*
  148.  * test whether the array element symbol[subs] exists or not 
  149.  */
  150. int
  151. in_array(symbol, subs)
  152. NODE *symbol, *subs;
  153. {
  154.     register int hash1;
  155.  
  156.     if (symbol->type == Node_param_list)
  157.         symbol = stack_ptr[symbol->param_cnt];
  158.     if (symbol->var_array == 0)
  159.         return 0;
  160.     subs = concat_exp(subs);    /* concat_exp returns a string node */
  161.     hash1 = hash(subs->stptr, subs->stlen);
  162.     if (assoc_find(symbol, subs, hash1) == NULL) {
  163.         free_temp(subs);
  164.         return 0;
  165.     } else {
  166.         free_temp(subs);
  167.         return 1;
  168.     }
  169. }
  170.  
  171. /*
  172.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  173.  * SUBS is a number or string used as the subscript. 
  174.  *
  175.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  176.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  177.  */
  178. NODE **
  179. assoc_lookup(symbol, subs)
  180. NODE *symbol, *subs;
  181. {
  182.     register int hash1;
  183.     register NODE *bucket;
  184.  
  185.     (void) force_string(subs);
  186.     hash1 = hash(subs->stptr, subs->stlen);
  187.  
  188.     if (symbol->var_array == 0) {    /* this table really should grow
  189.                      * dynamically */
  190.         unsigned size;
  191.  
  192.         size = sizeof(NODE *) * HASHSIZE;
  193.         emalloc(symbol->var_array, NODE **, size, "assoc_lookup");
  194.         memset((char *)symbol->var_array, 0, size);
  195.         symbol->type = Node_var_array;
  196.     } else {
  197.         bucket = assoc_find(symbol, subs, hash1);
  198.         if (bucket != NULL) {
  199.             free_temp(subs);
  200.             return &(bucket->ahvalue);
  201.         }
  202.     }
  203.  
  204.     /* It's not there, install it. */
  205.     if (do_lint && subs->stlen == 0)
  206.         warning("subscript of array is null string");
  207.     getnode(bucket);
  208.     bucket->type = Node_ahash;
  209.     bucket->ahname = dupnode(subs);
  210.     free_temp(subs);
  211.     bucket->ahvalue = Nnull_string;
  212.     bucket->ahnext = symbol->var_array[hash1];
  213.     symbol->var_array[hash1] = bucket;
  214.     return &(bucket->ahvalue);
  215. }
  216.  
  217. void
  218. do_delete(symbol, tree)
  219. NODE *symbol, *tree;
  220. {
  221.     register int hash1;
  222.     register NODE *bucket, *last;
  223.     NODE *subs;
  224.  
  225.     if (symbol->type == Node_param_list)
  226.         symbol = stack_ptr[symbol->param_cnt];
  227.     if (symbol->var_array == 0)
  228.         return;
  229.     subs = concat_exp(tree);    /* concat_exp returns string node */
  230.     hash1 = hash(subs->stptr, subs->stlen);
  231.  
  232.     last = NULL;
  233.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  234.         if (cmp_nodes(bucket->ahname, subs) == 0)
  235.             break;
  236.     free_temp(subs);
  237.     if (bucket == NULL)
  238.         return;
  239.     if (last)
  240.         last->ahnext = bucket->ahnext;
  241.     else
  242.         symbol->var_array[hash1] = bucket->ahnext;
  243.     unref(bucket->ahname);
  244.     unref(bucket->ahvalue);
  245.     freenode(bucket);
  246. }
  247.  
  248. void
  249. assoc_scan(symbol, lookat)
  250. NODE *symbol;
  251. struct search *lookat;
  252. {
  253.     if (!symbol->var_array) {
  254.         lookat->retval = NULL;
  255.         return;
  256.     }
  257.     lookat->arr_ptr = symbol->var_array;
  258.     lookat->arr_end = lookat->arr_ptr + HASHSIZE;    /* added */
  259.     lookat->bucket = symbol->var_array[0];
  260.     assoc_next(lookat);
  261. }
  262.  
  263. void
  264. assoc_next(lookat)
  265. struct search *lookat;
  266. {
  267.     while (lookat->arr_ptr < lookat->arr_end) {
  268.         if (lookat->bucket != 0) {
  269.             lookat->retval = lookat->bucket->ahname;
  270.             lookat->bucket = lookat->bucket->ahnext;
  271.             return;
  272.         }
  273.         lookat->arr_ptr++;
  274.         if (lookat->arr_ptr < lookat->arr_end)
  275.             lookat->bucket = *(lookat->arr_ptr);
  276.         else
  277.             lookat->retval = NULL;
  278.     }
  279.     return;
  280. }
  281.